#include <iostream>
#include <vector>
using namespace std;

/**
 * 高精度加法函数（处理大数相加）
 * @param a 第一个加数的逆序数字数组（例如：123存为[3,2,1]）
 * @param b 第二个加数的逆序数字数组
 * @return 和值的逆序数字数组
 */
vector<int> add(vector<int>& a, vector<int>& b) {
    vector<int> res;    // 存储结果的数组
    int carry = 0;      // 进位标志
    
    // 逐位相加直到处理完所有位数且无进位
    for (int i = 0; i < a.size() || i < b.size() || carry; i++) {
        // 累加当前位的数值
        if (i < a.size()) carry += a[i];
        if (i < b.size()) carry += b[i];
        
        // 存储当前位的结果并计算进位
        res.push_back(carry % 10);
        carry /= 10;    // 进位值传递给下一位
    }
    return res;
}

int main() {
    int n;
    cin >> n;  // 读取楼梯阶数
    
    // 处理边界情况：当n=0时直接返回0（根据题目特殊要求）
    if (n == 0) {
        cout << 0;
        return 0;
    }
    
    /* 动态规划数组初始化说明：
     * dp[i] 表示走到第i阶台阶的方法数（使用逆序存储的大数）
     * 数组大小设为n+3是为了防止越界访问（当n=1时至少需要dp[1]存在）
     */
    vector<vector<int>> dp(n + 3);
    
    // 初始化基础状态
    dp[0] = {1};  // 第0阶（地面）只有1种方法：不迈步
    dp[1] = {1};  // 第1阶只能从地面走1步到达
    
    // 动态规划递推过程
    for (int i = 2; i <= n; i++) {
        // 状态转移方程：dp[i] = dp[i-1] + dp[i-2]
        dp[i] = add(dp[i-1], dp[i-2]);
    }
    
    // 输出结果（逆序输出即为正确的大数顺序）
    for (int i = dp[n].size()-1; i >= 0; i--) {
        cout << dp[n][i];
    }
    
    return 0;
}

/* 
代码设计要点解析：
1. 高精度存储方案：
   - 使用vector<int>存储数字的每一位
   - 逆序存储便于处理进位（例如：123存为[3,2,1]）
   - 每位数字范围0-9，符合十进制表示

2. 动态规划优化：
   - 状态定义：dp[i]表示到达第i阶的方法数
   - 转移方程：dp[i] = dp[i-1] + dp[i-2]
   - 时间复杂度：O(n) 次加法操作，每次加法O(k)（k为数字位数）

3. 边界条件处理：
   - n=0的特殊情况直接处理
   - dp[0]初始化为1（算法数学基础）
   
4. 大数处理能力：
   - 可支持n=5000的计算（题目要求）
   - 不会出现整数溢出问题
*/